package 查找;

import java.util.Random;

public class 总类别 {
    public static void main(String[] args) {
        int[] arr = {1, 23, 34, 56, 78, 90, 98, 100, 123, 145, 167, 189, 1000};
        
        Random r = new Random();
        int[] newarry = new int[10000000];
        for (int i = 0; i < newarry.length; i++) {
            newarry[i] = r.nextInt(10000000);
        }

        int number = 1000;
        //1.基本查找basicSearch
        long a = System.nanoTime();
        System.out.println(basicSearch(arr, number));
        System.out.println(System.nanoTime() - a);
        System.out.println("--------------------------------------");
        //2.二分查找/折半查找
        long b = System.nanoTime();
        System.out.println(binarySearch(newarry, number));
        System.out.println(System.nanoTime() - b);
        System.out.println("--------------------------------------");
        //3.分块查找
        /*核心思想：块内无序，块间有序
        实现步骤：
        1.创建数组blcokArr存放每一个块对象信息
        2.确定查找的数值在哪一块blockArr
        3.单独遍历查找该块数组
        */
        int[] arr01 = {1, 12, 9, 13,
                23, 20, 19, 30, 29,
                40, 38, 50, 56, 49};
        int number01 = 49;
        blockSearch(arr01, number01);

    }

    private static void blockSearch(int[] arr01, int number01) {
        Block b1 = new Block(13, 0, 3);
        Block b2 = new Block(30, 4, 8);
        Block b3 = new Block(56, 9, 13);

        Block[] barr = {b1, b2, b3};

        int blockIndex = findIndex(barr, number01);
        if (number01 == barr[blockIndex].getMax()) {
            System.out.println(blockIndex);
            return;
        }
        int stratIndex = barr[blockIndex].getStartIndex();
        int endIndex = barr[blockIndex].getEndIndex();
        for (int i = stratIndex; i <= endIndex; i++) {
            if (number01 == arr01[i]) {
                System.out.println(i);
                return;
            }

        }
        System.out.println("没有找到");
    }

    private static int findIndex(Block[] barr, int number01) {
        if (number01 > barr[barr.length - 1].getMax()) {
            return -1;
        }
        for (int i = 0; i < barr.length; i++) {
            if (number01 < barr[i].getMax()) {
                return i;
            }
        }
        return -1;
    }

    static class Block {
        private int max;
        private int startIndex;
        private int endIndex;

        public Block() {
        }

        public Block(int max, int startIndex, int endIndex) {
            this.max = max;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        public int getMax() {
            return max;
        }

        public void setMax(int max) {
            this.max = max;
        }

        public int getStartIndex() {
            return startIndex;
        }

        public void setStartIndex(int startIndex) {
            this.startIndex = startIndex;
        }

        public int getEndIndex() {
            return endIndex;
        }

        public void setEndIndex(int endIndex) {
            this.endIndex = endIndex;
        }
    }

    private static boolean basicSearch(int[] arr, int number) {
        for (int i = 0; i < arr.length; i++) {
            if (number == arr[i]) {
                return true;
            }
        }
        return false;
    }

    private static int binarySearch(int[] arr, int number) {
        int min = 0;
        int max = arr.length - 1;
        if (arr[max] < number)
            return -1;
        //类似递归
        while (true) {
            if (min > max) {
                return -1;
            }
            /*核心逻辑*/
            int mid = (min + max) / 2;
            if (arr[mid] > number) { //左边
                max = mid - 1;
            } else if (arr[mid] < number) { //右边
                min = mid + 1;
            } else {
                return mid; //出口
            }
        }
    }
}
